繼第 7 天的「64. Minimum Path Sum」，今天來解 19 這題！還沒看過第 7 天或再之前天數的朋友，歡迎也去看看~

話不多說，我們開始吧！

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/remove-nth-node-from-end-of-list/

演算法與資料結構

• Linked List
• Two Pointers

題意

給予一個 linked list 的 head 節點，和一個 n。

請只移除從尾巴數來的第 n 節點，回傳 head 。

範例

head = [1, 2, 3, 4, 5]
n = 2

移除倒數第二個元素
答為

[1, 2, 3, 5]

思維

以這組數列和 n 為例

[0, 1, 2]
n = 1

用 dummy head 維持對 head 的參照

在 linked list ，我們經常利用一個 dummy head 節點來連結 head 以維持參照。避免在走訪期間我們失去 head 的參照

走訪邏輯

由於 linked list 無法直接指定 index 來移除

因此解決方法會是放置兩個 pointers 在 n 的 左 1 和 右 1：

L -> n -> R

1. 先讓 右 從 dummy 移動 n + 1 個位置
2. 讓 左 和 右 一起移動
3. 當 右 為 nil 時，代表走訪完成。這時候 左 的 next 就是需要被移除的節點
4. 將 左 .next 連上 左 .next?.next 即可完成

圖像解釋

以上面的例， n = 1

初始狀態後，先把輔助用的 right 放定位

  d          * right
+---+---+  +---+---+  +---+---+
| 0 | *-+->| 1 | *-+->| 2 | * |
+---+---+  +---+---+  +---+---+

接著一起移動

  d  
  |                    
  v 
  * left                * right
+---+---+  +---+---+  +---+---+
| 0 | *-+->| 1 | *-+->| 2 | * |
+---+---+  +---+---+  +---+---+

直到 right 為 nil 時停止，這時候就會得到需要移除值是 1 的節點。

  d
  | 
  v          * left                * right (nil)
+---+---+  +---+---+  +---+---+
| 0 | *-+->| 1 | *-+->| 2 | * |
+---+---+  +---+---+  +---+---+

調整完節點後如下

  d
  |
  v
+---+---+  +---+---+  +---+---+
| 0 | *-+->| 1 | * |  | 2 | * |    
+---+---+  +---+-+-+  +---+---+    ^ 
                 |                 |
                 +-----------------+

結果如下，為傳 dummy?.next 即為結果

  d
  |
  v
+---+---+  +---+---+
| 0 | *-+->| 1 | * |
+---+---+  +---+-+-+

程式碼

接著就可以開始寫程式碼了：

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy: ListNode? = ListNode(0)
        dummy?.next = head
        
        var right = dummy
        var left = dummy
        
        for _ in 0...n {
            right = right?.next
        }
        
        while right != nil {
            left = left?.next
            right = right?.next
        }
        
        left?.next = left?.next?.next
        return dummy?.next
    }
}

執行結果

• Runtime: 3ms (Beats 90.72%)
• Memory: 13.88MB (Beats 64.37%)

複雜度分析

令 n 為 linked list 節點的總數。

結語

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！